package cn.cas.mango.util.dbscan;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class DBSCAN {
    List<Data> allData;
    List<Cluster> clusters;
  // 中心节点的最小阈值为1
    private final int minPts = 1;
    private Map<String, List<Data>> neighborsMap;

    private DBSCAN() {
        this.allData = new ArrayList<>();
        this.clusters = new ArrayList<>();
    }
    public DBSCAN(List<Data> allData) {
        this();
        this.allData.addAll(allData);
    }



    /**
     * 实现dbscan算法
     * @param e，聚合因子
     * @return 返回最终聚合的结果
     */
    public Map<String, List<String>> run(double e) {
        neighborsMap = new GenerateAllNeighbors(allData, e).getAll();
      for (Data data : allData) {
        if (data.isVisited() || data.isAdded()) {
          continue;
        }
        List<Data> neighbors = getNeighbors(data);
        if (neighbors.isEmpty()) {

        } else {
          Cluster cluster = new Cluster(data);
          clusters.add(cluster);
          expand(neighbors, cluster);
        }
      }
        for (Data data: allData) {
            if (!data.isAdded()) {
                clusters.add(new Cluster(data));
            }
        }
        Collections.sort(clusters);
        return getIds();
    }

    /**
     * 将数据转换成id，方便后序映射
     * @return
     */
    private Map<String, List<String>> getIds() {
        Map<String, List<String>> ret = new LinkedHashMap<>();
        for (Cluster cluster: clusters) {
          String coreId = cluster.getCore().getId();
          ret.put(coreId, cluster.getNeighborsId());
        }
        return ret;
    }

    /**
     * 将第一个数据的邻居，及邻居中“中心节点”的所有邻居加入簇
     * @param neighbors，簇中第一个数据的邻居
     * @param cluster，需要扩张的簇
     */
    void expand(List<Data> neighbors, Cluster cluster) {
      HashSet<Data> nowNeighbors = new HashSet<>(neighbors);
        for (int i = 0; i < neighbors.size(); i++) {
            Data p = neighbors.get(i);
            if (!p.isAdded()) {
                cluster.add(p);
                p.setAdded();
            }
            if (!p.isVisited()) {
                p.setVisited();
                List<Data> secondNeighbors = getNeighbors(p);
                if (secondNeighbors.size() >= minPts) {
                    for (Data secondNeighbor: secondNeighbors) {
                        if (!secondNeighbor.isAdded() && !nowNeighbors.contains(secondNeighbor)) {
                            neighbors.add(secondNeighbor);
                            nowNeighbors.add(secondNeighbor);
                        }
                    }
                }
            }

        }
    }

    /**
     *
     * @param data, 输入data
     * @return data的所有邻居
     */
    private List<Data> getNeighbors(Data data) {
      return neighborsMap.get(data.getId());
    }


}
